home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / networking / info-service / wais / ir-book-sources / stopper / stop.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-04-08  |  26.5 KB  |  631 lines
  1.  
  2. /*********************************   stop.c   ********************************
  3.  
  4.     Purpose:     Stop list filter finite state machine generator and driver.
  5.  
  6.     Provenence:  Written by and unit tested by C. Fox, 1990.
  7.                  Changed by C. Fox, July 1991.
  8.                     - added ANSI C declarations
  9.                     - branch tested to 95% coverage
  10.  
  11.     Notes:       This module implements a fast finite state machine 
  12.                  generator, and a driver, for implementing stop list 
  13.                  filters.  The strlist module is a simple string array
  14.                  data type implementation.
  15. **/
  16.  
  17. #include <stdio.h>
  18. #include <ctype.h>
  19. #include <string.h>
  20. #include <malloc.h>
  21.  
  22. #include "stop.h"
  23. #include "strlist.h"
  24.  
  25. /******************************************************************************/
  26.  
  27. #define FALSE                        0
  28. #define TRUE                         1
  29. #define EOS                        '\0'
  30.  
  31.          /**************   Character Classification   ***************/
  32.          /* Tokenizing requires that ASCII be broken into character */
  33.          /* classes distinguished for tokenizing.  Delimiter chars  */
  34.          /* separate tokens.  Digits and letters make up the body   */
  35.          /* of search terms.                                        */
  36.  
  37. typedef enum {
  38.  
  39.                 DELIM_CH,              /* whitespace, punctuation, etc. */
  40.                 DIGIT_CH,              /* the digits */
  41.                 LETTER_CH,             /* upper and lower case */
  42.  
  43.             } CharClassType;
  44.  
  45. static CharClassType char_class[128] = {
  46.       /* ^@ */  DELIM_CH,    /* ^A */  DELIM_CH,    /* ^B */  DELIM_CH,
  47.       /* ^C */  DELIM_CH,    /* ^D */  DELIM_CH,    /* ^E */  DELIM_CH,
  48.       /* ^F */  DELIM_CH,    /* ^G */  DELIM_CH,    /* ^H */  DELIM_CH,
  49.       /* ^I */  DELIM_CH,    /* ^J */  DELIM_CH,    /* ^K */  DELIM_CH,
  50.       /* ^L */  DELIM_CH,    /* ^M */  DELIM_CH,    /* ^N */  DELIM_CH,
  51.       /* ^O */  DELIM_CH,    /* ^P */  DELIM_CH,    /* ^Q */  DELIM_CH,
  52.       /* ^R */  DELIM_CH,    /* ^S */  DELIM_CH,    /* ^T */  DELIM_CH,
  53.       /* ^U */  DELIM_CH,    /* ^V */  DELIM_CH,    /* ^W */  DELIM_CH,
  54.       /* ^X */  DELIM_CH,    /* ^Y */  DELIM_CH,    /* ^Z */  DELIM_CH,
  55.       /* ^[ */  DELIM_CH,    /* ^\ */  DELIM_CH,    /* ^] */  DELIM_CH,
  56.       /* ^^ */  DELIM_CH,    /* ^_ */  DELIM_CH,    /*    */  DELIM_CH,
  57.       /*  ! */  DELIM_CH,    /*  " */  DELIM_CH,    /*  # */  DELIM_CH,
  58.       /*  $ */  DELIM_CH,    /*  % */  DELIM_CH,    /*  & */  DELIM_CH,
  59.       /*  ' */  DELIM_CH,    /*  ( */  DELIM_CH,    /*  ) */  DELIM_CH,
  60.       /*  * */  DELIM_CH,    /*  + */  DELIM_CH,    /*  , */  DELIM_CH,
  61.       /*  - */  DELIM_CH,    /*  . */  DELIM_CH,    /*  / */  DELIM_CH,
  62.       /*  0 */  DIGIT_CH,    /*  1 */  DIGIT_CH,    /*  2 */  DIGIT_CH,
  63.       /*  3 */  DIGIT_CH,    /*  4 */  DIGIT_CH,    /*  5 */  DIGIT_CH,
  64.       /*  6 */  DIGIT_CH,    /*  7 */  DIGIT_CH,    /*  8 */  DIGIT_CH,
  65.       /*  9 */  DIGIT_CH,    /*  : */  DELIM_CH,    /*  ; */  DELIM_CH,
  66.       /*  < */  DELIM_CH,    /*  = */  DELIM_CH,    /*  > */  DELIM_CH,
  67.       /*  ? */  DELIM_CH,    /*  @ */  DELIM_CH,    /*  A */  LETTER_CH,
  68.       /*  B */  LETTER_CH,   /*  C */  LETTER_CH,   /*  D */  LETTER_CH,
  69.       /*  E */  LETTER_CH,   /*  F */  LETTER_CH,   /*  G */  LETTER_CH,
  70.       /*  H */  LETTER_CH,   /*  I */  LETTER_CH,   /*  J */  LETTER_CH,
  71.       /*  K */  LETTER_CH,   /*  L */  LETTER_CH,   /*  M */  LETTER_CH,
  72.       /*  N */  LETTER_CH,   /*  O */  LETTER_CH,   /*  P */  LETTER_CH,
  73.       /*  Q */  LETTER_CH,   /*  R */  LETTER_CH,   /*  S */  LETTER_CH,
  74.       /*  T */  LETTER_CH,   /*  U */  LETTER_CH,   /*  V */  LETTER_CH,
  75.       /*  W */  LETTER_CH,   /*  X */  LETTER_CH,   /*  Y */  LETTER_CH,
  76.       /*  Z */  LETTER_CH,   /*  [ */  DELIM_CH,    /*  \ */  DELIM_CH,
  77.       /*  ] */  DELIM_CH,    /*  ^ */  DELIM_CH,    /*  _ */  DELIM_CH,
  78.       /*  ` */  DELIM_CH,    /*  a */  LETTER_CH,   /*  b */  LETTER_CH,
  79.       /*  c */  LETTER_CH,   /*  d */  LETTER_CH,   /*  e */  LETTER_CH,
  80.       /*  f */  LETTER_CH,   /*  g */  LETTER_CH,   /*  h */  LETTER_CH,
  81.       /*  i */  LETTER_CH,   /*  j */  LETTER_CH,   /*  k */  LETTER_CH,
  82.       /*  l */  LETTER_CH,   /*  m */  LETTER_CH,   /*  n */  LETTER_CH,
  83.       /*  o */  LETTER_CH,   /*  p */  LETTER_CH,   /*  q */  LETTER_CH,
  84.       /*  r */  LETTER_CH,   /*  s */  LETTER_CH,   /*  t */  LETTER_CH,
  85.       /*  u */  LETTER_CH,   /*  v */  LETTER_CH,   /*  w */  LETTER_CH,
  86.       /*  x */  LETTER_CH,   /*  y */  LETTER_CH,   /*  z */  LETTER_CH,
  87.       /*  { */  DELIM_CH,    /*  | */  DELIM_CH,    /*  } */  DELIM_CH,
  88.       /*  ~ */  DELIM_CH,    /* ^? */  DELIM_CH,                          };
  89.  
  90.          /**************   Character Case Conversion   **************/
  91.          /* Term text must be accumulated in a single case.  This   */
  92.          /* array is used to convert letter case but otherwise      */
  93.          /* preserve characters.                                    */
  94.  
  95. static char convert_case[128] = {
  96.       /* ^@ */    0,    /* ^A */    0,    /* ^B */    0,    /* ^C */    0,
  97.       /* ^D */    0,    /* ^E */    0,    /* ^F */    0,    /* ^G */    0,
  98.       /* ^H */    0,    /* ^I */    0,    /* ^J */    0,    /* ^K */    0,
  99.       /* ^L */    0,    /* ^M */    0,    /* ^N */    0,    /* ^O */    0,
  100.       /* ^P */    0,    /* ^Q */    0,    /* ^R */    0,    /* ^S */    0,
  101.       /* ^T */    0,    /* ^U */    0,    /* ^V */    0,    /* ^W */    0,
  102.       /* ^X */    0,    /* ^Y */    0,    /* ^Z */    0,    /* ^[ */    0,
  103.       /* ^\ */    0,    /* ^] */    0,    /* ^^ */    0,    /* ^_ */    0,
  104.       /*    */  ' ',    /*  ! */  '!',    /*  " */  '"',    /*  # */  '#',
  105.       /*  $ */  '$',    /*  % */  '%',    /*  & */  '&',    /*  ' */ '\'',
  106.       /*  ( */  '(',    /*  ) */  ')',    /*  * */  '*',    /*  + */  '+',
  107.       /*  , */  ',',    /*  - */  '-',    /*  . */  '.',    /*  / */  '/',
  108.       /*  0 */  '0',    /*  1 */  '1',    /*  2 */  '2',    /*  3 */  '3',
  109.       /*  4 */  '4',    /*  5 */  '5',    /*  6 */  '6',    /*  7 */  '7',
  110.       /*  8 */  '8',    /*  9 */  '9',    /*  : */  ':',    /*  ; */  ';',
  111.       /*  < */  '<',    /*  = */  '=',    /*  > */  '>',    /*  ? */  '?',
  112.       /*  @ */  '@',    /*  A */  'a',    /*  B */  'b',    /*  C */  'c',
  113.       /*  D */  'd',    /*  E */  'e',    /*  F */  'f',    /*  G */  'g',
  114.       /*  H */  'h',    /*  I */  'i',    /*  J */  'j',    /*  K */  'k',
  115.       /*  L */  'l',    /*  M */  'm',    /*  N */  'n',    /*  O */  'o',
  116.       /*  P */  'p',    /*  Q */  'q',    /*  R */  'r',    /*  S */  's',
  117.       /*  T */  't',    /*  U */  'u',    /*  V */  'v',    /*  W */  'w',
  118.       /*  X */  'x',    /*  Y */  'y',    /*  Z */  'z',    /*  [ */  '[',
  119.       /*  \ */   92,    /*  ] */  ']',    /*  ^ */  '^',    /*  _ */  '_',
  120.       /*  ` */  '`',    /*  a */  'a',    /*  b */  'b',    /*  c */  'c',
  121.       /*  d */  'd',    /*  e */  'e',    /*  f */  'f',    /*  g */  'g',
  122.       /*  h */  'h',    /*  i */  'i',    /*  j */  'j',    /*  k */  'k',
  123.       /*  l */  'l',    /*  m */  'm',    /*  n */  'n',    /*  o */  'o',
  124.       /*  p */  'p',    /*  q */  'q',    /*  r */  'r',    /*  s */  's',
  125.       /*  t */  't',    /*  u */  'u',    /*  v */  'v',    /*  w */  'w',
  126.       /*  x */  'x',    /*  y */  'y',    /*  z */  'z',    /*  { */  '{',
  127.       /*  | */  '|',    /*  } */  '}',    /*  ~ */  '~',    /* ^? */    0, };
  128.  
  129. #define DEAD_STATE                    -1   /* used to block a DFA */
  130. #define TABLE_INCREMENT              256   /* used to grow tables */
  131.  
  132.  
  133.        /*************************   Hashing   **************************/
  134.        /* Sets of suffixes labeling states during the DFA construction */
  135.        /* are hashed to speed searching.  The hashing function uses an */
  136.        /* entire integer variable range as its hash table size;  in an */
  137.        /* effort to get a good spread through this range, hash values  */
  138.        /* start big, and are incremented by a lot with every new word  */
  139.        /* in the list.  The collision rate is low using this method    */
  140.  
  141. #define HASH_START               5775863
  142. #define HASH_INCREMENT          38873647
  143.  
  144.  
  145.        /**************   State Label Binary Search Tree   **************/
  146.        /* During DFA construction, all states must be searched by      */
  147.        /* their labels to make sure that the minimum number of states  */
  148.        /* are used.  This operation is sped up by hashing the labels   */
  149.        /* to a signature value, then storing the signatures and labels */
  150.        /* in a binary search tree.  The tree is destroyed once the DFA */
  151.        /* is fully constructed.                                        */
  152.  
  153. typedef struct TreeNode {
  154.        StrList label;            /* state label used as search key     */
  155.        unsigned signature;       /* hashed label to speed searching    */
  156.        int state;                /* whose label is representd by node  */
  157.        struct TreeNode *left;    /* left binary search subtree         */
  158.        struct TreeNode *right;   /* right binary search subtree        */
  159.        } SearchTreeNode, *SearchTree;
  160.  
  161.  
  162.        /*********************   DFA State Table   **********************/
  163.        /* The state table is an array of structures holding a state    */
  164.        /* label, a count of the arcs out of the state, a pointer into  */
  165.        /* the arc table for these arcs, and a final state flag.  The   */
  166.        /* label field is used only during machine construction.        */
  167.  
  168. typedef struct {
  169.        StrList label;            /* for this state - used during build */
  170.        int num_arcs;             /* for this state in the arc table    */
  171.        int arc_offset;           /* for finding arcs in the arc table  */
  172.        short is_final;           /* TRUE iff this is a final state     */
  173.        } StateTableEntry, *StateTable;
  174.  
  175.  
  176.        /**********************   DFA Arc Table   ***********************/
  177.        /* The arc table lists all transitions for all states in a DFA  */
  178.        /* in compacted form.  Each state's transitions are offset from */
  179.        /* the start of the table, then listed in arc label order.      */
  180.        /* Transitions are found by a linear search of the sub-section  */
  181.        /* of the table for a given state.                              */
  182.  
  183. typedef struct {
  184.        char label;               /* character label on an out-arrow    */
  185.        int target;               /* the target state for the out-arrow */
  186.        } ArcTableEntry, *ArcTable;
  187.  
  188.  
  189.        /**********************   DFA Structure   ***********************/
  190.        /* A DFA is represented as a pointer to a structure holding the */
  191.        /* machine's state and transition tables, and bookkeepping      */
  192.        /* counters.  The tables are arrays whose space is malloc'd,    */
  193.        /* then realloc'd if more space is required.  Once a machine is */
  194.        /* constructed, the table space is realloc'd one last time to   */
  195.        /* fit the needs of the machine exactly.                        */
  196.  
  197. typedef struct _DfaStruct {
  198.        int num_states;           /* in the DFA (and state table)       */
  199.        int max_states;           /* now allocated in the state table   */
  200.        int num_arcs;             /* in the arc table for this machine  */
  201.        int max_arcs;             /* now allocated in the arc table     */
  202.        StateTable state_table;   /* the compacted DFA state table      */
  203.        ArcTable arc_table;       /* the compacted DFA transition table */
  204.        SearchTree tree;          /* storing state labels used in build */
  205.        } DFAStruct;
  206.  
  207. /******************************************************************************/
  208. /*************************   Function Declarations   **************************/
  209.  
  210. #ifdef __STDC__
  211.  
  212. static char *GetMemory( char *ptr, int num_bytes );
  213. static void  DestroyTree( SearchTree tree );
  214. static int   GetState( DFA machine, StrList label, unsigned signature );
  215. static void  AddArc( DFA machine, int state, char arc_label,
  216.                      StrList state_label, unsigned state_signature );
  217.  
  218. extern DFA   BuildDFA( StrList words );
  219. extern char *GetTerm( FILE *stream, DFA machine, int size, char *output );
  220.  
  221. #else
  222.  
  223. static char *GetMemory();
  224. static void  DestroyTree();
  225. static int   GetState();
  226. static void  AddArc();
  227.  
  228. extern DFA   BuildDFA();
  229. extern char *GetTerm();
  230.  
  231. #endif
  232.  
  233. /******************************************************************************/
  234. /************************   Private Function Definitions   ********************/
  235.  
  236. /*FN***************************************************************************
  237.  
  238.         GetMemory( ptr, num_bytes )
  239.  
  240.    Returns: char * -- new/expanded block of memory
  241.  
  242.    Purpose: Rationalize memory allocation and handle errors
  243.  
  244.    Plan:    Part 1: Allocate memory with supplied allocation functions
  245.             Part 2: Handle any errors
  246.             Part 3: Return the allocated block of memory
  247.  
  248.    Notes:   None.
  249. **/
  250.  
  251. static char *
  252. GetMemory( ptr, num_bytes )
  253.    char *ptr;      /* in: expanded block; NULL if nonesuch */
  254.    int num_bytes;  /* in: number of bytes to allocate */
  255.    {
  256.    char *memory;   /* temporary for holding results */
  257.  
  258.         /* Part 1: Allocate memory with supplied allocation functions */
  259.    if ( NULL == ptr )
  260.       memory = malloc( (unsigned)num_bytes );
  261.    else
  262.       memory = realloc( ptr, (unsigned)num_bytes );
  263.  
  264.                     /* Part 2: Handle any errors */
  265.    if ( NULL == memory )
  266.       {
  267.       (void)fprintf( stderr, "malloc failure--aborting\n" );
  268.       exit(1);
  269.       }
  270.  
  271.              /* Part 3: Return the allocated block of memory */
  272.    return( memory );
  273.  
  274.    } /* GetMemory */
  275.  
  276. /*FN***************************************************************************
  277.  
  278.         DestroyTree( tree )
  279.  
  280.    Returns: void
  281.  
  282.    Purpose: Destroy a binary search tree created during machine construction
  283.  
  284.    Plan:    Part 1: Return right away of there is no tree
  285.             Part 2: Deallocate the subtrees
  286.             Part 3: Deallocate the root
  287.  
  288.    Notes:   None.
  289. **/
  290.  
  291. static void
  292. DestroyTree( tree )
  293.    SearchTree tree;   /* in: search tree destroyed */
  294.    {
  295.               /* Part 1: Return right away of there is no tree */
  296.    if ( NULL == tree ) return;
  297.  
  298.                      /* Part 2: Deallocate the subtrees */
  299.    if ( NULL != tree->left )  DestroyTree( tree->left );
  300.    if ( NULL != tree->right ) DestroyTree( tree->right );
  301.  
  302.                       /* Part 3: Deallocate the root */
  303.    tree->left = tree->right = NULL;
  304.    (void)free( (char *)tree );
  305.  
  306.    } /* DestroyTree */
  307.  
  308. /*FN***************************************************************************
  309.  
  310.         GetState( machine, label, signature )
  311.  
  312.    Returns: int -- state with the given label
  313.  
  314.    Purpose: Search a machine and return the state with a given state label
  315.  
  316.    Plan:    Part 1: Search the tree for the requested state
  317.             Part 2: If not found, add the label to the tree
  318.             Part 3: Return the state number
  319.  
  320.    Notes:   This machine always returns a state with the given label
  321.             because if the machine does not have a state with the given
  322.             label, then one is created.
  323. **/
  324.  
  325. static int
  326. GetState( machine, label, signature )
  327.    DFA machine;        /* in: DFA whose state labels are searched;
  328.    StrList label;      /* in: state label searched for */
  329.    unsigned signature; /* in: signature of the label requested */
  330.    {
  331.    SearchTree *ptr;       /* pointer to a search tree link field */
  332.    SearchTree new_node;   /* for a newly added search tree node */
  333.  
  334.              /* Part 1: Search the tree for the requested state */
  335.    ptr = &(machine->tree);
  336.    while ( (NULL != *ptr) && (   (signature != (*ptr)->signature)
  337.                               || !StrListEqual(label,(*ptr)->label)) )
  338.       ptr = (signature <= (*ptr)->signature) ? &(*ptr)->left : &(*ptr)->right;
  339.  
  340.              /* Part 2: If not found, add the label to the tree */
  341.    if ( NULL == *ptr )
  342.       {
  343.          /* create a new node and fill in its fields */
  344.       new_node = (SearchTree)GetMemory( NULL, sizeof(SearchTreeNode) );
  345.       new_node->signature = signature;
  346.       new_node->label = (StrList)label;
  347.       new_node->state = machine->num_states;
  348.       new_node->left = new_node->right = NULL;
  349.  
  350.          /* allocate more states if needed, set up the new state */
  351.       if ( machine->num_states == machine->max_states )
  352.          {
  353.          machine->max_states += TABLE_INCREMENT;
  354.          machine->state_table =
  355.            (StateTable)GetMemory( machine->state_table,
  356.                                   machine->max_states*sizeof(StateTableEntry));
  357.          }
  358.       machine->state_table[machine->num_states].label = (StrList)label;
  359.       machine->num_states++;
  360.  
  361.          /* hook the new node into the binary search tree */
  362.       *ptr = new_node;
  363.       }
  364.    else
  365.       StrListDestroy( label );
  366.  
  367.                    /* Part 3: Return the state number */
  368.    return( (*ptr)->state );
  369.  
  370.    } /* GetState */
  371.  
  372. /*FN***************************************************************************
  373.  
  374.         AddArc( machine, state, arc_label, state_label, state_signature )
  375.  
  376.    Returns: void
  377.  
  378.    Purpose: Add an arc between two states in a DFA
  379.  
  380.    Plan:    Part 1: Search for the target state among existing states
  381.             Part 2: Make sure the arc table is big enough
  382.             Part 3: Add the new arc
  383.  
  384.    Notes:   None.
  385. **/
  386.  
  387. static void
  388. AddArc( machine, state, arc_label, state_label, state_signature )
  389.    DFA machine;              /* in/out: machine with an arc added */
  390.    int state;                /* in: with an out arc added */
  391.    char arc_label;           /* in: label on the new arc */
  392.    StrList state_label;      /* in: label on the target state */
  393.    unsigned state_signature; /* in: label hash signature to speed searching */
  394.    {
  395.    register int target;   /* destination state for the new arc */
  396.  
  397.         /* Part 1: Search for the target state among existing states */
  398.    StrListSort( state_label );
  399.    target = GetState( machine, state_label, state_signature );
  400.  
  401.                /* Part 2: Make sure the arc table is big enough */
  402.    if ( machine->num_arcs == machine->max_arcs )
  403.       {
  404.       machine->max_arcs += TABLE_INCREMENT;
  405.       machine->arc_table =
  406.          (ArcTable)GetMemory( machine->arc_table,
  407.                               machine->max_arcs * sizeof(ArcTableEntry) );
  408.       }
  409.  
  410.                         /* Part 3: Add the new arc */
  411.    machine->arc_table[machine->num_arcs].label = arc_label;
  412.    machine->arc_table[machine->num_arcs].target = target;
  413.    machine->num_arcs++;
  414.    machine->state_table[state].num_arcs++;
  415.  
  416.    } /* AddArc */
  417.  
  418. /*FN***************************************************************************
  419.  
  420.         BuildDFA( words )
  421.  
  422.    Returns: DFA -- newly created finite state machine
  423.  
  424.    Purpose: Build a DFA to recognize a list of words
  425.  
  426.    Plan:    Part 1: Allocate space and initialize variables
  427.             Part 2: Make and label the DFA start state
  428.             Part 3: Main loop - build the state and arc tables
  429.             Part 4: Deallocate the binary search tree and the state labels
  430.             Part 5: Reallocate the tables to squish them down
  431.             Part 6: Return the newly constructed DFA
  432.  
  433.    Notes:   None.
  434. **/
  435.  
  436. DFA
  437. BuildDFA( words )
  438.    StrList words;  /* in: that the machine is built to recognize */
  439.    {
  440.    DFA machine;               /* local for easier access to machine */
  441.    register int state;        /* current state's state number */
  442.    char arc_label;            /* for the current arc when adding arcs */
  443.    char *string;              /* element in a set of state labels */
  444.    char ch;                   /* the first character in a new string */
  445.    StrList current_label;     /* set of strings labeling a state */
  446.    StrList target_label;      /* labeling the arc target state */
  447.    unsigned target_signature; /* hashed label for binary search tree */
  448.    register int i;            /* for looping through strings */
  449.  
  450.               /* Part 1: Allocate space and initialize variables */
  451.    machine = (DFA)GetMemory( NULL, sizeof(DFAStruct) );
  452.  
  453.    machine->max_states = TABLE_INCREMENT;
  454.    machine->state_table =
  455.       (StateTable)GetMemory(NULL, machine->max_states*sizeof(StateTableEntry));
  456.    machine->num_states = 0;
  457.  
  458.    machine->max_arcs = TABLE_INCREMENT;
  459.    machine->arc_table =
  460.       (ArcTable)GetMemory( NULL, machine->max_arcs * sizeof(ArcTableEntry) );
  461.    machine->num_arcs = 0;
  462.  
  463.    machine->tree = NULL;
  464.  
  465.                 /* Part 2: Make and label the DFA start state */
  466.    StrListUnique( words );               /* sort and unique the list */
  467.    machine->state_table[0].label = words;
  468.    machine->num_states = 1;
  469.  
  470.             /* Part 3: Main loop - build the state and arc tables */
  471.    for ( state = 0; state < machine->num_states; state++ )
  472.       {
  473.               /* The current state has nothing but a label, so */
  474.               /* the first order of business is to set up some */
  475.               /* of its other major fields                     */
  476.       machine->state_table[state].is_final = FALSE;
  477.       machine->state_table[state].arc_offset = machine->num_arcs;
  478.       machine->state_table[state].num_arcs = 0;
  479.  
  480.              /* Add arcs to the arc table for the current state */
  481.              /* based on the state's derived set.  Also set the */
  482.              /* state's final flag if the empty string is found */
  483.              /* in the suffix list                              */
  484.       current_label = machine->state_table[state].label;
  485.       target_label = StrListCreate();
  486.       target_signature = HASH_START;
  487.       arc_label = EOS;
  488.       for ( i = 0; i < StrListSize(current_label); i++ )
  489.          {
  490.             /* get the next string in the label and lop it */
  491.          string = StrListPeek( current_label, i );
  492.          ch = *string++;
  493.  
  494.             /* the empty string means mark this state as final */
  495.          if ( EOS == ch )
  496.             { machine->state_table[state].is_final = TRUE; continue; }
  497.  
  498.             /* make sure we have a legitimate arc_label */
  499.          if ( EOS == arc_label ) arc_label = ch;
  500.  
  501.             /* if the first character is new, then we must */
  502.             /* add an arc for the previous first character */
  503.          if ( ch != arc_label )
  504.             {
  505.             AddArc(machine, state, arc_label, target_label, target_signature);
  506.             target_label = StrListCreate();
  507.             target_signature = HASH_START;
  508.             arc_label = ch;
  509.             }
  510.  
  511.             /* add the current suffix to the target state label */
  512.          StrListAppend( target_label, string );
  513.          target_signature += (*string + 1) * HASH_INCREMENT;
  514.          while ( *string ) target_signature += *string++;
  515.          }
  516.  
  517.               /* On loop exit we have not added an arc for the */
  518.               /* last bunch of suffixes, so we must do so, as  */
  519.               /* long as the last set of suffixes is not empty */
  520.               /* (which happens when the current state label   */
  521.               /* is the singleton set of the empty string).    */
  522.       if ( 0 < StrListSize(target_label) )
  523.          AddArc( machine, state, arc_label, target_label, target_signature );
  524.       }
  525.  
  526.       /* Part 4: Deallocate the binary search tree and the state labels */
  527.    DestroyTree( machine->tree );  machine->tree = NULL;
  528.    for ( i = 0; i < machine->num_states; i++ )
  529.       {
  530.       StrListDestroy( machine->state_table[i].label );
  531.       machine->state_table[i].label = NULL;
  532.       }
  533.  
  534.             /* Part 5: Reallocate the tables to squish them down */
  535.    machine->state_table = (StateTable)GetMemory( machine->state_table,
  536.                                machine->num_states * sizeof(StateTableEntry) );
  537.    machine->arc_table = (ArcTable)GetMemory( machine->arc_table,
  538.                                machine->num_arcs * sizeof(ArcTableEntry) );
  539.  
  540.                 /* Part 6: Return the newly constructed DFA */
  541.    return( machine );
  542.  
  543.    } /* BuildDFA */
  544.  
  545. /*FN***************************************************************************
  546.  
  547.         GetTerm( stream, machine, size, output )
  548.  
  549.    Returns: char * -- NULL if stream is exhausted, otherwise output buffer
  550.  
  551.    Purpose: Get the next token from an input stream, filtering stop words
  552.  
  553.    Plan:    Part 1: Return NULL immediately if there is no input
  554.             Part 2: Initialize the local variables
  555.             Part 3: Main Loop: Put an unfiltered word into the output buffer
  556.             Part 4: Return the output buffer
  557.  
  558.    Notes:   This routine runs the DFA provided as the machine parameter,
  559.             and collects the text of any term in the output buffer.  If
  560.             a stop word is recognized in this process, it is skipped.
  561.             Care is also taken to be sure not to overrun the output buffer.
  562. **/
  563.  
  564. char *
  565. GetTerm( stream, machine, size, output )
  566.    FILE *stream;    /* in: source of input characters */
  567.    DFA machine;     /* in: finite state machine driving process */
  568.    int size;        /* in: bytes in the output buffer */
  569.    char *output;    /* in/out: where the next token in placed */
  570.    {
  571.    char *outptr;        /* for scanning through the output buffer */
  572.    int ch;              /* current character during input scan */
  573.    register int state;  /* current state during DFA execution */
  574.  
  575.            /* Part 1: Return NULL immediately if there is no input */
  576.    if ( EOF == (ch = getc(stream)) ) return( NULL );
  577.  
  578.                   /* Part 2: Initialize the local variables */
  579.    outptr = output;
  580.  
  581.      /* Part 3: Main Loop: Put an unfiltered word into the output buffer */
  582.    do
  583.       {
  584.          /* scan past any leading delimiters */
  585.       while ( (EOF != ch ) &&
  586.               ((DELIM_CH == char_class[ch]) ||
  587.                (DIGIT_CH == char_class[ch])) ) ch = getc( stream );
  588.  
  589.          /* start the machine in its start state */
  590.       state = 0;
  591.  
  592.          /* copy input to output until reaching a delimiter, and also */
  593.          /* run the DFA on the input to watch for filtered words      */
  594.       while ( (EOF != ch) && (DELIM_CH != char_class[ch]) )
  595.          {
  596.          if ( outptr == (output+size-1) ) { outptr = output; state = 0; }
  597.          *outptr++ = convert_case[ch];
  598.  
  599.          if ( DEAD_STATE != state )
  600.             {
  601.             register int i;   /* for scanning through arc labels */
  602.             int arc_start;    /* where the arc label list starts */
  603.             int arc_end;      /* where the arc label list ends */
  604.  
  605.             arc_start = machine->state_table[state].arc_offset;
  606.             arc_end = arc_start + machine->state_table[state].num_arcs;
  607.  
  608.             for ( i = arc_start; i < arc_end; i++ )
  609.                if ( convert_case[ch] == machine->arc_table[i].label )
  610.                   { state = machine->arc_table[i].target; break; }
  611.  
  612.             if ( i == arc_end ) state = DEAD_STATE;
  613.             }
  614.  
  615.          ch = getc( stream );
  616.          }
  617.  
  618.          /* start from scratch if a stop word is recognized */
  619.       if ( (DEAD_STATE != state) && machine->state_table[state].is_final )
  620.          outptr = output;
  621.  
  622.          /* terminate the output buffer */
  623.       *outptr = EOS;
  624.       }
  625.    while ( (EOF != ch) && !*output );
  626.  
  627.                     /* Part 4: Return the output buffer */
  628.    return( output );
  629.  
  630.    } /* GetTerm */
  631.